﻿#include "CTravellingSalesman.h"
#include <utility>
#include <limits>
#include <algorithm>
#include <Windows.h>
#include <WindowsX.h>
#include <WinGDI.h>

void CTravellingSalesman::getMinSpanningTree( vector< Vertex >& graph, vector< vector< int > >& _graph ) {
	//приводим в начальное состояние все вершины
	for( vector< Vertex >::iterator i = graph.begin(); i != graph.end(); ++i ){
        i->parent = NULL;
		i->paren = -1;
        i->cost = std::numeric_limits< double >::infinity();
        i->closed = false;
    }
	int m = 0;
	graph[0].cost = 0;//начинаем с 0 вершины
	for( int i = 0; i < graph.size(); ++i ) {
		Vertex* v = NULL;
		//ищем вершину с ребром наименьшей стоимости для нашей выбранной вершины
		for( int j = 0; j < graph.size(); ++j )
			if( !graph[j].closed && ( v == NULL || graph[j].cost < v->cost ) ) {
				//v = &( *j );
				v = &graph[j];
				m = j;
			}
		v->closed = true;// отметим, что побывали в ней
		if( v->parent != NULL ) {//добавляем ребро туда и обратно, чтобы эйлеров путь найти
			_graph[ graph[m].paren ].push_back( m );
			_graph[m].push_back( graph[m].paren );
		}
		// обновляем все стоимости до остальных вершин от выбранной
		for( int j = 0; j < graph.size(); j++ )
			if( v->getDistanse( &graph[j] ) < graph[j].cost ) {
				graph[j].cost = v->getDistanse( &graph[j] );
				graph[j].parent = v;
				graph[j].paren = m;
			}
	}
}

void CTravellingSalesman::getMinSpanningTree2( vector< Vertex >& graph, std::vector< std::vector< int > >& _graph ) {
    vector< pair< double, pair< int,int > > > edges;
	vector< int > tree_id( graph.size() );
    for( int i = 0; i < graph.size(); ++i ) {
            tree_id[i] = i;
    }
	//добавляем все ребр
    for( int i = 0; i < graph.size() - 1; ++i ) {
            for( int j = i + 1; j < graph.size(); ++j ) {
				edges.push_back( pair< double, pair< int,int > >( graph[i].getDistanse( &graph[j] ), pair< int, int >( i, j ) ) );
            }
    }
    sort( edges.begin(), edges.end() );//сортируем ребра по весу в порядке неубывания
	

    for( int i = 0; i < edges.size(); ++i ) {
            int a = edges[i].second.first, b = edges[i].second.second;
            if( tree_id[a] != tree_id[b] ) {
				_graph[a].push_back( b );
				_graph[b].push_back( a );
                int old_id = tree_id[b], new_id = tree_id[a];
                for( int j = 0; j < graph.size(); ++j ) {
                        if( tree_id[j] == old_id) {
                                tree_id[j] = new_id;
                        }
                }
            }
    }
}

void CTravellingSalesman::eulerianPath( vector< Vertex* >& way, vector< Vertex >& graph, std::vector< std::vector< int > >& _graph ) {
	stack< int > stackS;
	 int strt = 0;
	 set< pair< int, int > > closed;
     stackS.push( strt );
     while( !stackS.empty() ) {
		int u = stackS.top();
		bool allClosed = true;
		//ищем не помеченные ребра
		for( int i = 0; i < _graph[u].size(); ++i ) {
			pair< int, int > pr = make_pair( u, _graph[u][i] );
            if( closed.find( pr ) == closed.end() ) {//закрываем ве ребра из вершины и добавляем её детей
				allClosed = false;
                closed.insert( pr );
				stackS.push( _graph[u][i] );
			}
		}
        if( allClosed ) {// если все ребра из данной вершины уже были закрыты, то добавим вершину в путь
			way.push_back( &graph[u] );
            stackS.pop();
        }
	}

};

double CTravellingSalesman::TravellingSalesman( vector< Vertex >& graph, vector< Vertex* >& newWay, bool krusk ) {
    double summ = 0;
	std::vector< std::vector< int > > _graph;
	_graph.resize( graph.size() );
    map< Vertex*, list< Vertex* > > MST;
	if( krusk )
		getMinSpanningTree2( graph, _graph );//алгоритм Крускала
	else
		getMinSpanningTree( graph, _graph );//получаем MST пр алг Прима
    vector< Vertex* > way;
	for( int i = 0; i < graph.size(); ++i ) {
		std::sort( _graph[i].begin(), _graph[i].end() );
	}
    eulerianPath( way, graph, _graph );//получаем эйлеров путь по MST
	for( int i = 0; i < graph.size(); ++i ) {
		graph[i].closed = false;
	}

    Vertex* old;
    Vertex* next = *( way.begin() );
    newWay.push_back( next );

	
	next->closed = true;
	//записываем в newWay Эйлеров путь, с учетом того, чтобы не попадать в уже закрытые вершины
    for( vector< Vertex* >::iterator i = ++way.begin();  i != way.end(); ++i ) {
        old = next;
        while( i != way.end() && ( *i )->closed )
			i++;
        if( i == way.end() ) 
			break;
        next = *i;
		next->closed = true;
        newWay.push_back( next );
    }

    old = *newWay.begin();
    for( std::vector< Vertex* >::iterator y = ++newWay.begin(); y != newWay.end(); ++y ) {
         summ += old->getDistanse( *y );
         old = *y;
    }
    summ += newWay[ newWay.size() - 1 ]->getDistanse( newWay[0] );
    return summ;
}
